package leetcode.hot100;

import java.util.*;

public class Solution84 {

    //单调栈
    public int largestRectangleArea(int[] heights) {
        //为方便计算在首尾加上0
        ArrayList<Integer> heightList = new ArrayList<Integer>(heights.length);
        for (int num:heights){
            heightList.add(num);
        }
        heightList.add(0,0);
        heightList.add(0);
        //用栈存储单调元素的下标，记录计算面积时确定左边边界
        Stack<Integer> incrementStack = new Stack<>();
        int maxArea = 0;

        for (int i = 0; i < heightList.size(); i++) {
            if(incrementStack.empty()||heights[i]>=heights[incrementStack.peek()]){
                //当前柱子为高的矩形面积还无法计算
                //相当于单调栈入栈一个非减元素
                incrementStack.push(i);
            }
            while(!incrementStack.empty()&&heights[i]>heights[incrementStack.peek()]){
                //栈顶柱子为高的矩形面积可以确定了，左边界是栈里前一个下标
                int curHeight = heights[incrementStack.pop()]; //栈顶出栈，获取矩形高
                int curArea;
                if(incrementStack.empty()){  //是单根
                    curArea = curHeight*1;
                }else {
                    curArea = curHeight*(i-incrementStack.pop()-1);
                }
//                (i-incrementStack.peek());
//                maxArea = maxArea>
            }
        }


        return 0;
    }

}

class Solution {

    public int largestRectangleArea1(int[] heights) {
        int n = heights.length + 1;
        int[] heights0 = new int[n];
        for (int i = 0; i < n - 1; i++) heights0[i] = heights[i];
        int[] scan = new int[n + 1];
        scan[0] = -1;
        int l = 0, r = 0, ans = 0;
        while (r < n) {
            while (l > 0 && heights0[r] < heights0[scan[l]]) {
                int h = heights0[scan[l--]];
                ans = Math.max(ans, h * (r - scan[l] - 1));
            }
            scan[++l] = r++;
        }
        return ans;
    }

    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) {
            return 0;
        }

        if (len == 1) {
            return heights[0];
        }

        int res = 0;

        int[] newHeights = new int[len + 2];
        newHeights[0] = 0;
        System.arraycopy(heights, 0, newHeights, 1, len);
        newHeights[len + 1] = 0;
        len += 2;
        heights = newHeights;

        Deque<Integer> stack = new ArrayDeque<>(len);
        // 先放入哨兵，在循环里就不用做非空判断
        stack.addLast(0);

        for (int i = 1; i < len; i++) {
            while (heights[i] < heights[stack.peekLast()]) {
                int curHeight = heights[stack.pollLast()];
                int curWidth = i - stack.peekLast() - 1;
                res = Math.max(res, curHeight * curWidth);
            }
            stack.addLast(i);
        }
        return res;
    }
}
